/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-01-23 11:15:16
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-01-23 22:42:21
 * @FilePath: \LeetCode\15.三数之和.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=15 lang=cpp
 *
 * [15] 三数之和
 *
 * 方法1：nums[i] + nums[j] == -nums[k]
 * 1. num_k == 0 时如何移动指针
 * 2. 指针越界 [0,0,0,0] 无解
 *
 * 官方题解：nums[j] + nums[k] == -nums[i]
 * - 外层循环 i 跳过重复元素
 * - 内存循环 j k 使用双指针
 */

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// @lc code=start
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> result;
        int pre[2] = {1, 1};  // 用于去重

        std::sort(nums.begin(), nums.end());

        for (auto i = nums.begin(); *i <= 0 && i != nums.end(); i++)
        {
            for (auto j = nums.end() - 1; *j >= 0 && i < j; j--)
            {
                int num_k = -((*i) + (*j));
                if ((pre[0] != (*i) || pre[1] != (*j)) &&
                    std::binary_search(i + 1, j, num_k))
                {
                    pre[0] = (*i);
                    pre[1] = (*j);
                    result.push_back({(*i), num_k, (*j)});
                }
            }
        }

        return result;
    }

    vector<vector<int>> threeSum_00(vector<int> &nums)
    {
        vector<vector<int>> result;

        std::sort(nums.begin(), nums.end());

        int len = nums.size();
        int i, j, k, target, sum;
        for (i = 0; i < len; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1]) // 外层去重
                continue;

            target = -nums[i];

            /* 双指针相互限制 */
            j = i + 1;
            k = len - 1;
            while (j < k)
            {
                sum = nums[j] + nums[k];
                if (sum == target)
                {
                    result.push_back({nums[i], nums[j], nums[k]});
                    j++;
                    k--;
                    /* 跳过重复元素 */
                    while (j < k && nums[j] == nums[j - 1])
                        j++;
                    while (j < k && nums[k] == nums[k + 1])
                        k--;
                }
                else if (sum < target)
                    j++;
                else
                    k--;
            }
        }

        return result;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    vector<int> nums = {0, 0, 0, 0};

    vector<vector<int>> result = solution.threeSum(nums);
    for (auto v : result)
    {
        for (auto n : v)
            cout << n << ", ";
        cout << endl;
    }

    return 0;
}